//package work.rightAnswer;
//
//
//
//import work.TreeNode;
//
//import java.util.ArrayList;
//import java.util.LinkedList;
//import java.util.List;
//
//class Solution_103 {
//    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
//        LinkedList<TreeNode> queue =new LinkedList<>();
//        queue.offer(root);
//        List<List<Integer>> res = new ArrayList<>();
//        if(root==null){
//            return res;
//        }
//        //利用双向链表
//        //1.从左到右：queue.offerFirst 先左节点再右节点 ,读取 queue.pollLast
//        //2.从右到左：queue.offerLast 先右节点再左节点 ,读取 queue.pollFist
//        //设置boolean变量flag，默认为true ，true 为从左到右遍历，false 为 从右到左遍历 每回合结束后：flag = flag==true?false:true;
//        boolean flag = true;
//        while (!queue.isEmpty()){
//            int size = queue.size();
//            List<Integer> list = new ArrayList<>();
//            if(flag) {
//                for (int i = 0; i < size; i++) {
//                    TreeNode pollLast = queue.pollLast();
//                    list.add(pollLast.val);
//                    if(pollLast.left!=null)queue.offerFirst(pollLast.left);
//                    if(pollLast.right!=null)queue.offerFirst(pollLast.right);
//                }
//            }else {
//                for (int i = 0; i < size; i++) {
//                    TreeNode pollFirst = queue.pollFirst();
//                    list.add(pollFirst.val);
//                    if(pollFirst.right!=null) queue.offerLast(pollFirst.right);
//                    if(pollFirst.left!=null) queue.offerLast(pollFirst.left);
//                }
//            }
//            res.add(list);
//            flag = flag==true?false:true;
//        }
//        return res;
//    }
//}